package LeetCode.Leet400_499.Leet450_459.Leet452;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/5/26 11:24
 * @Description TODO: 方法一    模拟（贪心） 58ms    57.15%
 */
class Solution_1 {
    public int findMinArrowShots(int[][] points) {
        // 排序，便于后续计算，按照X_start升序排序，X_start相同则按照X_end降序排序
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o2[1] - o1[1];
            }
        });

        int count = 0;
        int startIndex = points[0][0];
        int endIndex = points[0][1];
        for (int i = 0; i < points.length; i++) {
            // 记录，在[startIndex, endIndex]内射击可以击破前面未击破的气球
            startIndex = Math.max(startIndex, points[i][0]);
            endIndex = Math.min(endIndex, points[i][1]);
            // 一旦tartIndex > endIndex了，那么前面的气球和此气球后面的气球一次无法全部击破
            if (startIndex > endIndex) {
                count++;  // 射击次数+1
                // 后面的气球重新累计
                startIndex = points[i][0];
                endIndex = points[i][1];
            }
        }
        count++;  // 剩余的气球需要一次射击
        return count;
    }
}
